#include <iostream>
#include <vector>

using namespace std;

class Solution
{
public:
	int GetfarestStation(vector<int>& gas, vector<int>& cost, int start)
	{
		int len = gas.size();
		int release = gas[start];
		int step = 0;
		for (step = 1; step < len+1; step++)
		{
			int gasIndex = (start + step) % len;
			int costIndex = (start + step - 1) % len;
			release -= cost[costIndex];
			if (release < 0)
			{
				return step-1;
			}
			release += gas[gasIndex];
		}
		return step-1;
	}
	int canCompleteCircuit(vector<int>& gas, vector<int>& cost)
	{
		int len = gas.size();
		int start = 0;
		while (start<len)
		{
			int length=GetfarestStation(gas, cost, start);
			if (length == len)
			{
				return start;
			}
			start += length+1;
		}
		return -1;
	}

	int canCompleteCircuit_overtime(vector<int>& gas, vector<int>& cost)
	{
		int len = gas.size();
		for (int i = 0; i < len; i++)
		{
			int release = gas[i];
			bool flag = true;
			for (int step = 1; step < len+1; step++)
			{
				int gasIndex = (i + step) % len;
				int costIndex = (i + step - 1) % len;
				release -= cost[costIndex];
				if (release < 0)
				{
					flag = false;
					break;
				}
				release += gas[gasIndex];
			}
			if (flag)
			{
				return i;
			}
		}
		return -1;
	}
};

int main()
{
	cout << "code134" << endl;
	std::vector<int> gas{ 1, 2, 3, 4, 5 };
	std::vector<int>cost{ 3, 4, 5, 1, 2 };
	Solution s;
	//cout << s.GetfarestStation(gas, cost, 0) << endl;
	//cout << s.GetfarestStation(gas, cost, 1) << endl;
	//cout << s.GetfarestStation(gas, cost, 2) << endl;
	//cout << s.GetfarestStation(gas, cost, 3) << endl;
	//cout << s.GetfarestStation(gas, cost, 4) << endl;
	cout << s.canCompleteCircuit(gas, cost) << endl;
	return 0;
}